#include <iostream>

#define N 7
typedef int ElemType;

void Merge(ElemType A[], int low, int mid, int high)
{
    static ElemType B[N];
    int i,j,k;
    for(i=low;i<=high;i++)//把A[i]里的元素都给B[i]中
    {
        B[i]=A[i];
    }
    k=low;
    for(i=low,j=mid+1; i<=mid&&j<=high; )//合并两个数组
    {
        if(B[i]<B[j])
        {
            A[k]=B[i];
            i++;
            k++;
        }
        else
        {
            A[k]=B[j];
            j++;
            k++;
        }
    }
    //把某一个有序数组中剩余的元素放进来
    while(i<=mid)//前一半有剩余的元素放入
    {
        A[k]=B[i];
        i++;
        k++;
    }
    while(j<=high)//后一半有剩余的元素放入
    {
        A[k]=B[j];
        j++;
        k++;
    }
}


//归并排序不限制两两归并，还是多个归并，考研都是考两两归并
void MergeSort(ElemType A[], int low, int high)
{
    if(low<high)
    {
        int mid = (low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}

void Print(ElemType A[])
{
    int i = 0;
    for(i=0;i<N;i++)
    {
        printf("%3d",A[i]);
    }
    printf("\n");
}

// 空间复杂度O(N)
int main()
{
    int A[7]={49,38,65,97,76,13,27};//数组，7个元素
    Print(A);
    MergeSort(A, 0, 6);
    Print(A);

    return 0;
}
